package com.leetcode;

import java.util.*;

/**
 * 451. 根据字符出现频率排序
 * 按照出现频率排序
 *
 * @author fy
 * @date 2022/4/7 16:05
 */
public class Solution451 {

    private class Node {
        public int count;
        public char ch;

        public Node(char ch, int count) {
            this.ch = ch;
            this.count = count;
        }
    }

    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        Queue<Node> heap = new PriorityQueue<>(Comparator.comparingInt(a -> -a.count));
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            heap.offer(new Node(entry.getKey(), entry.getValue()));
        }
        StringBuilder sb = new StringBuilder();
        while (!heap.isEmpty()) {
            Node node = heap.poll();
            for (int i = 0; i < node.count; i++) {
                sb.append(node.ch);
            }
        }
        return sb.toString();
    }

    /**
     * 简化版本
     *
     * @param s
     * @return
     */
    public String frequencySort1(String s) {
        final Map<Character, Integer> map = new HashMap<>(s.length());
        Queue<Character> heap = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            heap.offer(entry.getKey());
        }
        StringBuilder sb = new StringBuilder();
        while (!heap.isEmpty()) {
            char ch = heap.poll();
            for (int i = 0; i < map.get(ch); i++) {
                sb.append(ch);
            }
        }
        return sb.toString();
    }

    /**
     * 使用Collections 自定义 Comparator 排序
     *
     * @param s
     * @return
     */
    public String frequencySort2(String s) {
        final Map<Character, Integer> map = new HashMap<>(s.length());
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        List<Character> chList = new ArrayList<>(map.keySet());
        Collections.sort(chList, (a, b) -> map.get(b) - map.get(a));
        StringBuilder sb = new StringBuilder();
        for (Character ch : chList) {
            for (int i = 0; i < map.get(ch); i++) {
                sb.append(ch);
            }
        }
        return sb.toString();
    }
}
